package com.review.backpack_01;

public class BP05 {
    //5. 二维费用的背包问题
    //物品拥有体积质量和价值
    public int knapsackProblem(int[] volume, int maxV, int[] weight, int maxW, int[] value) {
        int[][] dp = new int[maxV + 1][maxW + 1];
        for (int i = 0; i < volume.length; i++) {
            for (int j = maxV; j >= volume[i]; j--) {
                for (int k = maxW; k >= weight[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - volume[i]][k - weight[i]] + value[i]);
                }
            }
        }
        return dp[maxV][maxW];
    }

    public static void main(String[] args) {
        System.out.println(
                new BP05().knapsackProblem(
                        new int[]{1, 2, 3, 4},
                        5,
                        new int[]{2, 4, 4, 5},
                        6,
                        new int[]{3, 4, 5, 6}
                )
        );
    }
}
